package com.limeng.datastruts.alth.binary;

import java.util.LinkedList;
import java.util.Stack;

public class BinarySearchDemo {

    /**
     *
     * @param nums 查找数组
     * @param num  目标值
     * @return     目标值下标
     */
    public static int binarySearch(int[] nums, int num){
        return binarySearchUnit(nums,0,nums.length-1,num);
    }

    private static int binarySearchUnit(int[] nums, int low, int high, int num) {

        if (nums.length < 3) return -1;
        if (low > high) return -1;

        int mid = (low + high) / 2;
        if(nums[mid] == num){
            return mid;
        }else if(num < nums[mid]){
            return binarySearchUnit(nums,low,mid-1,num);
        }else{
            return binarySearchUnit(nums,mid+1,high,num);
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,3,5,7,9,13,16,19,22};
        System.out.println(binarySearch(nums,19));
    }

    public int calPoints(String[] ops) {
        int result = 0;
        Stack<String> stack = new Stack<String>();
        for(int i=0;i<ops.length;i++){
            String obj = ops[i];
            if(obj.equals("+")){
                int numPlus1 = Integer.parseInt(stack.pop());
                int numPlus2 = Integer.parseInt(stack.pop());
                stack.add(numPlus1*numPlus2+"");
            }else if(obj.equals("D")){
                int numD = Integer.parseInt(stack.peek());
                stack.push(numD*2+"");
            }else if(obj.equals("C")){
                String numC = stack.pop();
                stack.pop();
                stack.push(numC);
            }else{
                stack.push(obj);
            }
        }
        for(String num:stack){
            result+=Integer.parseInt(num);
        }
        return result;
    }

}
